/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
 //根据中序和后序构造二叉树 关于如何确定左右子树，统一按照左右根的顺序  前序中序后序的顺序
 //都是先访问中序递归
class Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
            if (postorder.empty())
            {
                return nullptr;
            }

            int leftpost = 0, rightpost = postorder.size();
            int leftin = 0, rightin = inorder.size() - 1;

            //先申请出根节点
            TreeNode* root = new TreeNode(postorder[postorder.size() - 1]);

            //分别存放左右子树
            vector<int> leftv;
            vector<int> rightv;

            //开始存放中序的右子树
            for (int i = 0; i < inorder.size(); i++)
            {
                if (inorder[i] != postorder[postorder.size() - 1])
                {
                    leftv.push_back(inorder[i]);
                }
                else
                {
                    break;
                }
            }
            int idx1 = 0, idx2 = 0;
            idx1 = leftv.size();

            //把左子树在放进去
            for (int i = 0; i < idx1; i++)
            {
                rightv.push_back(postorder[i]);
            }
            idx2 = rightv.size();

            root->left = buildTree(leftv, rightv);

            //清空数据
            leftv.clear();
            rightv.clear();

            //右边的处理  
            for (int i = idx2; i < postorder.size() - 1; i++)
            {
                rightv.push_back(postorder[i]);
            }

            for (int i = idx1 + 1; i < inorder.size(); i++)  //别把for循环写错了
            {
                leftv.push_back(inorder[i]);
            }
            root->right = buildTree(leftv, rightv);


            return root;
        }
    
};